//
// Created by isabella on 25-5-27.
//
#include <common.h>

class Graph {
public:
    vector<vector<int> > _g;
    int _n;
    int inf = INT_MAX / 2;

    Graph(int n, vector<vector<int> > &edges) {
        _g = vector(n, vector(n, inf));
        for (int i = 0; i < n; i++) {
            _g[i][i] = 0;
        }
        _n = n;
        for (const auto & edge : edges) {
            int from = edge[0], to = edge[1], weight = edge[2];
            _g[from][to] = weight;
        }
        for (int k = 0; k < _n; k++) {
            for (int i = 0; i < _n; i++) {
                for (int j = 0; j < _n; j++) {
                    _g[i][j] = min(_g[i][j], _g[i][k] + _g[k][j]);
                }
            }
        }
    }

    void addEdge(vector<int> edge) {
        int from = edge[0], to = edge[1], weight = edge[2];
        _g[from][to] = weight;
        for (int k = 0; k < _n; k++) {
            for (int i = 0; i < _n; i++) {
                for (int j = 0; j < _n; j++) {
                    _g[i][j] = min(_g[i][j], _g[i][k] + _g[k][j]);
                }
            }
        }
    }

    int shortestPath(int node1, int node2) {
        return _g[node1][node2]==inf?-1:_g[node1][node2];
    }
};


int main() {
    vector<vector<int>> data={
        {0, 2, 5},
        {0, 1, 2},
        {1, 2, 1},
        {3, 0, 3}
    };
    auto sp = new Graph(4, data);
    cout<<sp->shortestPath(3,2)<<endl;
    cout<<sp->shortestPath(0,3)<<endl;
    vector<int> e={1,3,4};
    sp->addEdge(e);
    cout<<sp->shortestPath(0,3)<<endl;
    return 0;
}
